#pragma once


template <typename ElementType>
class Deque
{
public:
	Deque()
	{
		m_pHead = m_pTail = NULL;
		m_nSize = 0;
	}

	~Deque(){}

	ElementType PopHead()
	{
		ElementType e;
		if (NULL != m_pHead)
		{
			e = m_pHead->m_Value;
			Node* pNext = m_pHead->m_pNext;
			delete m_pHead;
			m_pHead = NULL;
			m_pHead = pNext;
			--m_nSize;
		}
		return e;
	}

	ElementType GetHead()
	{
		ElementType e;
		if (NULL != m_pHead)
		{
			e = m_pHead->m_Value;
		}
		return e;
	}

	void PushHead(ElementType e)
	{
		Node* pNode = new Node;
		pNode->m_Value = e;
		pNode->m_pNext = m_pHead;
		if (NULL != m_pHead)
		{
			m_pHead->m_pFront = pNode;
		}

		m_pHead = pNode;
		if (NULL == m_pTail)
		{
			m_pTail = m_pHead;
		}
		++m_nSize;
	}

	ElementType PopTail()
	{
		ElementType e;
		if (NULL != m_pTail)
		{
			e = m_pTail->m_Value;
			Node* pFront = m_pTail->m_pFront;
			delete m_pTail;
			m_pTail = NULL;
			m_pTail = pFront;
			--m_nSize;
		}
		return e;
	}

	ElementType GetTail()
	{
		ElementType e;
		if (NULL != m_pTail)
		{
			e = m_pTail->m_Value;
		}
		return e;
	}

	void PushTail(ElementType e)
	{
		Node* pNode = new Node;
		pNode->m_Value = e;
		pNode->m_pFront = m_pTail;
		if (NULL != m_pTail)
		{
			m_pTail->m_pNext = pNode;
		}

		m_pTail = pNode;
		if (NULL == m_pHead)
		{
			m_pHead = m_pTail;
		}
		++m_nSize;
	}

	void Clear()
	{
		Node* pNode = NULL;
		while(NULL != m_pHead)
		{
			pNode = m_pHead->m_pNext;
			delete m_pHead;
			m_pHead = NULL;
			m_pHead = pNode;
		}
		m_nSize = 0;
	}

	int GetSize()
	{
		return m_nSize;
	}

	bool IsEmpty()
	{
		return (0 == m_nSize);
	}

	template<typename Func>
	void Ergodic(Func func, bool bFromHead=true)
	{
		Node* pNode = (bFromHead ? m_pHead : m_pTail);
		while(NULL != pNode)
		{
			func(pNode->m_Value);
			pNode = (bFromHead ? pNode->m_pNext : pNode->m_pFront);
		}
	}

private:
	typedef struct _Node
	{
		_Node():m_pFront(NULL),m_pNext(NULL){}

		ElementType m_Value;
		struct _Node* m_pFront;
		struct _Node* m_pNext;
	}Node;

	Node* m_pHead;
	Node* m_pTail;
	int m_nSize;
};

bool PrintAll(int n)
{
	std::cout << n << " ";
	return true;
}

void Test_Deque()
{
	Deque<int>* pDeque = new Deque<int>;
	pDeque->PushHead(1);
	pDeque->PushHead(2);
	pDeque->PushHead(3);
	pDeque->PushTail(4);
	pDeque->PushTail(5);
	std::cout << "Size: " << pDeque->GetSize() << std::endl;

	pDeque->Ergodic(PrintAll);
	
	std::cout << "PopHead: " << pDeque->PopHead() << std::endl;
	std::cout << "GetHead: " << pDeque->GetHead() << std::endl;
	std::cout << "PopTail: " << pDeque->PopTail() << std::endl;
	std::cout << "GetTail: " << pDeque->GetTail() << std::endl;

	std::cout << "Size: " << pDeque->GetSize() << std::endl;

	pDeque->Clear();
}
